import java.util.ArrayList;
import java.util.List;

/**
 * 763. Partition Labels 划分字母区间
 * https://leetcode.com/problems/partition-labels/description/
 */
class PartitionLabels {
    /**
     * 方法：划分字符串为尽可能多的部分，使得每个字母最多出现在一个部分中
     * Args: 
     *   s: 输入字符串
     * Returns: 
     *   包含每个部分长度的列表
     * Time: O(n)，其中n是字符串的长度
     * Space: O(1)，只使用了固定大小的数组
     */
    public List<Integer> partitionLabels(String s) {
        char[] charS = s.toCharArray();
        int n = s.length();
        int[] last = new int[26];
        for(int i = 0; i< n; i++){
            last[charS[i] - 'a'] = i; // 每个字母最后出现的下标
        }
        List<Integer> ans = new ArrayList<>();
        int start = 0, end = 0;
        for(int i = 0; i < n; i++){
            end = Math.max(end, last[charS[i] - 'a']);
            if(end == i){
                ans.add(end - start + 1);
                start = i + 1;
            }
        }
        return ans;
    }
}